package com.zlk.algorithm.huawei.leetcode.dimidiate;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName Code56_searchMatrix
 * @description:
 * @author: slfang
 * @create: 2025-01-20 15:05
 * @Version 1.0
 **/
public class Code56_searchMatrix {


    @Test
    public void test(){
//        int[][] ma = new int[][]{
//                {1,3,5,7},{10,11,16,20},{23,30,34,60}
//        };
        int [][] ma = new int[][]{
                {1}
        };
        //searchMatrix(ma,13);
        searchMatrix(ma,1);
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int m = matrix[0].length;
        int[] row = new int[n];
        for (int i = 0; i < n; i++) {
            row[i] = matrix[i][0];
        }
        int rowIndex = findMostRight(row,target);
        if(rowIndex==-1){
            return false;
        }
        return findMid(matrix[rowIndex],target)!=-1;

    }

    private int findMid(int[] matrix, int target) {
        int l = 0;
        int r = matrix.length-1;
        int m;
        int ans = -1;
        while (l<=r){
            m = l+(r-l)/2;
            if(target<matrix[m]){
                r = m-1;
            }else if(target>matrix[m]){
                l = m+1;
            }else{
                ans = m;
                break;
            }
        }
        return ans;
    }

    //  3 3 3
    private int  findMostRight(int[] row, int target) {
        int l = 0;
        int r = row.length-1;
        int m;
        int ans = -1;
        while (l<=r){
            m = l+(r-l)/2;
            if(target>=row[m]){
                ans = m;
                l = m+1;
            }else{
                r = m-1;
            }
        }
        return ans;
    }
}
